#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "automata.h"
#include "util.h"
#include "testInputs.h"
#include "longInt.h"
#define NO_DEBUG

#ifdef DEBUG
    #define DEBUGM  printf
#else
    #define DEBUGM  //
#endif

int 
main(int argc, char *argv[])
{
    t_table t;
    FILE * fIn, * fOut;
    char fileName[50];
    int i,aux;
       
    if(argc!=2)
        error(1,"Use: blabla file\n(file must have \"in\" extension)");

    strncpy(fileName, argv[1], 50);

    if((fIn = fopen(strcat(fileName,".in"),"r"))==NULL)
        error(1,"Could not open file. Check file name is correct.");
    
    t = parseFile(fIn);


#ifdef DEBUG
    printf("\n\nAfter parsing file ----------------------\n");
    //Display transition table
    printTable(&t);
    printf("\nStates involved:\n");
    //Print states
    printStates2(&t.states);
    printf("\nFinal states:\n");
    //Print final states
    printStates2(&t.finalStates);
    system("pause");
#endif    

    printf("Removing Lambda...\n");
    removeLambdaTrans(&t);
    
#ifdef DEBUG
    printf("\n\nAfter lambda transitions removed ----------------------\n");
    //Display transition table
    printTable(&t);
    printf("\nStates involved:\n");
    //Print states
    printStates2(&t.states);
    printf("\nFinal states:\n");
    //Print final states
    printStates2(&t.finalStates);
    system("pause");
#endif
   
    printf("Determinization...\n");
    nfaToDfa(&t);

#ifdef DEBUG
    printf("\n\nAfter determinization----------------------\n");
    //Display transition table
    printTable(&t);
    printf("\nStates involved:\n");
    //Print states
    printStates2(&t.states);
    printf("\nFinal states:\n");
    //Print final states
    printStates2(&t.finalStates);
    system("pause");
#endif
    
    printf("Minimizing...\n");    
    MinimizeDFA(&t);

#ifdef DEBUG    
    printf("\n\nAfter minimization----------------------\n");
    printTable(&t);
    system("pause");
#endif

    printf("Evaluating chains...\n");    
    testInput(&t);

    printf("Writing output file...\n");    
    i = strlen(fileName);
    strcpy(fileName + i - 2, "out");
    if((fOut = fopen(fileName, "w"))==NULL)
        error(1,"Could not open file for writing");
    writeFile(fOut,&t);
    fclose(fOut);
    
    //Releasing memory
    free(t.alphabet);
    for(i=0;i<t.input.dim;i++)
        free(t.input.chains[i]);
    free(t.input.chains);
    free(t.finalStates.vec);
    free(t.states.vec);
    for(i=0;i<t.transitions.fils;i++)
        free(t.transitions.data[i]);
    free(t.transitions.data);

    #ifdef DEBUG
        system("pause");
    #endif

    printf("\nEVERYTHING DONE\n");    
    
    return 0;
}

t_matrix
buildMatrix(int fil, int col)
{
    int i,j;
    t_matrix out;
    
    out.fils=fil;
    out.dimFils=fil+30;
    out.cols=col;
    if((out.data = malloc(sizeof(int *)*out.dimFils))== NULL)
        error(1,"Could not allocate memory. Shame on you.");
    
    for(i=0;i<out.dimFils;i++)
        out.data[i]=malloc(sizeof(int)*col);

    //Fill matrix with -1 which means the trap/error state transition
    for(i=0;i<out.dimFils;i++)
        for(j=0;j<col;j++)
            out.data[i][j] = -1;
            
    return out;
}


void
writeFile(FILE * f, t_table * t)
{
    int i, j, st, alphabetDim;
    
    alphabetDim = strlen(t->alphabet);
    
    //Print Alphabet
    fprintf(f,"%s\n",t->alphabet);

    //Print number of states
    fprintf(f,"%d\n",t->states.dim);

    //Print initial state
    fprintf(f,"%d\n",t->iniState);

    //Print final states
    if (t->finalStates.dim > 0)
    {
        for(i=0;i<t->finalStates.dim-1;i++)
            fprintf(f,"%d ",getStateIndex(t,t->finalStates.vec[i]));
        fprintf(f,"%d\n",getStateIndex(t,t->finalStates.vec[i]));
    }
    else fprintf(f, "\n"); 
        

    //Print transitions
    for(i=0;i<t->transitions.fils;i++)
        for(j=0;j<alphabetDim;j++)
            if ((st = t->transitions.data[i][j]) != -1)
                fprintf(f,"%d %d %c\n",i, st,t->alphabet[j]);
                
    fprintf(f,"\n");
    for(i=0;i<t->input.dim-1;i++)
        fprintf(f,"%s\n",t->input.chains[i]);
    fprintf(f,"%s",t->input.chains[i]);
}

t_table 
parseFile(FILE * f)
{
    t_table t;
    t_matrix m;
    t_int_vector v;
    t_input in;
    char c, * alpha, buf[BUF_SIZE], buf2[BUF_SIZE], * toks, symbol;
    int cantSym, from_state, to_state, symbol_index, i, ilen;
    void * aux;
    t_longInt_vector livec, liFinvec;

    DEBUGM("PARSE: Line 1...\n");        
    //Reading alphabet - 1st line
    if((alpha = malloc(BUF_SIZE))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    cantSym = getline(alpha, BUF_SIZE, f);
    if((aux = realloc(alpha, cantSym + 1))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    else
        t.alphabet = aux;

    DEBUGM("PARSE: Line 2...\n");
    //2nd line - states
    getline(buf,BUF_SIZE,f);
    t.originalDim = atoi(buf);
    if(t.originalDim > 255)
        error(1,"Not able to process NFA with more than 255 states\n");
    createVec(&livec,atoi(buf));
    t.states=livec;
    t.states.dim=atoi(buf);
    for(i=0;i<t.states.dim;i++)
        turnOn(t.states.vec[i],i);
    
    DEBUGM("PARSE: Line 3...\n");
    //3rd line
    getline(buf,BUF_SIZE,f);
    t.iniState = atoi(buf);
    
    DEBUGM("PARSE: Line 4...\n");
    //4th line
    getline(buf,BUF_SIZE,f);
    strcpy(buf2,buf);
    toks = strtok(buf," ");
    i=0;
    while(toks != NULL)
    {
        i++;
        toks = strtok(NULL," ");
    }
    
    t.originalFinalDim=i;
    
    createVec(&liFinvec,i);
    t.finalStates=liFinvec;
    t.finalStates.dim=i;
    
    i=0;
    toks = strtok(buf2," ");
    while(toks != NULL)
    {
        turnOn(t.finalStates.vec[i],atoi(toks));
        i++;
        toks = strtok(NULL," ");
    }
    
    //Build transitions matrix
    m = buildMatrix(t.states.dim,cantSym+1); //add extra symbol: lambda
    t.transitions = m;

    DEBUGM("PARSE: Line 5 till blank...\n");        
    //Rest of the file, until input lines
    while(getline(buf,BUF_SIZE,f))
    {
        from_state = atoi(strtok(buf," "));
        to_state = atoi(strtok(NULL," "));
        if((toks = strtok(NULL," "))==NULL) //Lambda transition
            symbol = '^';
        else
            symbol = *toks;
        if(from_state > t.states.dim-1 || to_state > t.states.dim-1)
            error(1,"Malformed input file - using more states than declared");
        symbol_index = getSymIndex(t.alphabet,symbol);
        addTransition(&t,from_state,symbol_index,to_state);
    }
    
    DEBUGM("PARSE: Inputs after blank...\n");        
    //Input chains for processing
    if((in.chains = malloc(10 * sizeof(char *)))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    in.dim = 0;
    while(1)
    {
        if((ilen=getline(buf,BUF_SIZE,f))==0 && *buf != '\0')
            break;

        if ((in.chains[in.dim] = malloc(ilen + 1)) == NULL)
            error(1,"Could not allocate memory. Shame on you.");
        
        strncpy(in.chains[in.dim], buf, ilen);
        in.chains[in.dim][ilen] = 0;
        
        in.dim++;
        
        //Need to allocate more space
        if(in.dim%10 == 0)
        {
            if((aux = realloc(in.chains, (in.dim+10)*sizeof(char *)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
            else
                in.chains = aux;
        }
    }
    
    t.input = in;
   
    fclose(f);
    
DEBUGM("PARSE: DONE. Returning\n");        
    
    return t;
}

int
getSymIndex(char * alphabet, char symbol)
{
    int i,len;

    len=strlen(alphabet);

    //If it's a lambda transition, then return last matix column index    
    if(symbol == '^')
        return len;
    
    for(i=0;i<len;i++)
        if(alphabet[i] == symbol)
            break;
    
    return i;
}

void
addTransition(t_table * t, int from_state, int symbol_index, int to_state)
{
    int state, prevSt, aux;
    t_longInt l;

    prevSt = t->transitions.data[from_state][symbol_index];
    if(prevSt == -1)
    {
        t->transitions.data[from_state][symbol_index] = to_state;
        return ;
    }

    longIntCpy(l,t->states.vec[prevSt]);
    turnOn(l,to_state);

    
    t->transitions.data[from_state][symbol_index] = 
        getStateIndex(t, l);            
}

int
getStateIndex(t_table * t, t_longInt l)
{
    int i, j, found;
    t_longInt acum;
    void * aux;
    
    for(i=0,found=0;i<t->states.dim;i++)
        if(longIntCmp(t->states.vec[i],l))
        {
            found=1;
            break;
        }

    //Add a new state
    if(!found)
    {
        //Allocate more space if needed
        if(t->states.dim == t->states.maxDim)
        {
            if((aux=realloc(t->states.vec,
                sizeof(t_longInt)* (t->states.maxDim *= 2)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
            else
                t->states.vec = aux;
        }
        //Add new state into states vector
        longIntCpy(t->states.vec[t->states.dim++],l);        
    
        //Check if new state is an acceptance one, then add it
        reset(acum);
        for(j=0;j<t->originalFinalDim;j++)
            longIntMerge(acum,t->finalStates.vec[j]);
        
        longIntAnd(acum,l);
        if(!isZero(acum))
        {
            //Allocate more space if needed
            if(t->finalStates.dim == t->finalStates.maxDim)
            {
                if((aux=realloc(t->finalStates.vec,
                    sizeof(t_longInt)* (t->finalStates.maxDim *= 2)))==NULL)
                    error(1,"Could not allocate memory. Shame on you.");
                else
                    t->finalStates.vec=aux;
            }
            //Add new state into final states vector
            longIntCpy(t->finalStates.vec[t->finalStates.dim++],l);
        }          
    } 

    return i;
}

int
getline(char * line, int max, FILE * f)
{
    int cant;

    if(fgets(line, max, f)==NULL)
        return 0;

    return RemoveReturnWLM(line);
}

void
removeLambdaTrans(t_table * t)
{
    int i, j, m, n, alphabetDim, cl, newState, aux, aux2, myself, mergeWith;
    t_longInt closure, checked, newSt, newSt2;
    t_longInt_vector closures;
    
    alphabetDim = strlen(t->alphabet);
  
    //Calculates Lambda Closures and adds final states discovered
    createVec(&closures,t->originalDim);
    for(i=0;i<t->originalDim;i++)
    {
        reset(checked);
        setLambdaClosure(i,t,closures.vec[i],checked);
        longIntMerge(closures.vec[i],t->states.vec[i]);
        closures. dim++;
        checkFinalInClosure(t,closures.vec[i],i);
    }
#ifdef DEBUG
    printf("------------------>\n");
    printf("Clausuras Lambda:\n");
    printStates2(&closures);
    printf("<------------------\n");
    system("pause");
#endif

    for(i=0;i<t->originalDim;i++)
    {  
        for(j=0;j<alphabetDim;j++)
        {
            myself = t->transitions.data[i][j];
            reset(newSt);
            reset(newSt2);
            if(myself != -1)
                longIntMerge(newSt,t->states.vec[myself]);
            for(m=0;m<CANT_INT;m++)
            {
                if(closures.vec[i][m]!=0)
                    for(n=0;n<32;n++)
                        if(1<<n & closures.vec[i][m])
                        {
                            mergeWith = t->transitions.data[n+32*m][j];
                            if(mergeWith != -1)
                                longIntMerge(newSt,t->states.vec[mergeWith]);
                        }
            }
            for(m=0;m<CANT_INT;m++)
                if(newSt[m]!=0)
                    for(n=0;n<32;n++)
                        if(1<<n & newSt[m])
                            longIntMerge(newSt2,closures.vec[n+32*m]);
            longIntMerge(newSt,newSt2);
            if(!isZero(newSt))
                t->transitions.data[i][j] = getStateIndex(t,newSt);
        }        
    }
    for(i=0;i<t->originalDim;i++)
        t->transitions.data[i][alphabetDim]=-1;
    recheckFinalStates(t);
}

void
checkFinalInClosure(t_table * t, t_longInt closure, int state)
{
    int i,j;
    t_longInt acum;
    t_longInt_vector lvec;
    
    reset(acum);
    for(i=0;i<t->originalFinalDim;i++)
        longIntMerge(acum,t->finalStates.vec[i]);
        
    longIntAnd(acum,closure);
    if(!isZero(acum) && !isFinalStInd(t,state))
    {
        createVec(&lvec,t->finalStates.dim+1);
        for(i=0;i<t->originalFinalDim;i++)
            longIntCpy(lvec.vec[i],t->finalStates.vec[i]);
        turnOn(lvec.vec[i++],state);
        for(j=i-1;j<t->finalStates.dim;j++)
            longIntCpy(lvec.vec[i++],t->finalStates.vec[j]);
        lvec.dim=t->finalStates.dim+1;
        free(t->finalStates.vec);
        t->originalFinalDim++;
        t->finalStates=lvec;
    }
}

void
recheckFinalStates(t_table * t)
{
    int i;
    t_longInt acum, aux;
    void * aux2;
    
    reset(acum);
    for(i=0;i<t->originalFinalDim;i++)
        longIntMerge(acum,t->finalStates.vec[i]);

    for(i=t->originalDim;i<t->states.dim;i++)
    {
        longIntCpy(aux,acum);
        longIntAnd(aux,t->states.vec[i]);
        if(!isZero(aux) && !isFinalStInd(t,i))
        {
            //Allocate more space if needed
            if(t->finalStates.dim == t->finalStates.maxDim)
            {
                if((aux2=realloc(t->finalStates.vec,
                    sizeof(t_longInt)* (t->finalStates.maxDim *= 2)))==NULL)
                    error(1,"Could not allocate memory. Shame on you.");
                else
                    t->finalStates.vec=aux2;
            }
            //Add new state into final states vector
            longIntCpy(t->finalStates.vec[t->finalStates.dim++],t->states.vec[i]);
        }
    }
        
}

void
setLambdaClosure(int state, t_table * t, t_longInt closure, t_longInt checked)
{
    int i, j, lambdaTo, alphabetDim;

    alphabetDim = strlen(t->alphabet);
    lambdaTo = t->transitions.data[state][alphabetDim];
    if(lambdaTo == -1 || lambdaTo == state || alreadySeen(lambdaTo,t->originalDim,checked))
        return ;

    turnOn(checked,state);
    
    if(lambdaTo >= t->originalDim)
    {
        for(i=0;i<CANT_INT;i++)
            for(j=0;j<32;j++)
                if(1<<j & (t->states.vec[lambdaTo])[i])
                {
                    if(alreadySeen(j+32*i,t->originalDim,checked))
                        continue;
                    t->transitions.data[state][alphabetDim] = j+32*i;
                    setLambdaClosure(state,t,closure,checked);
                }
        //Restore info
        t->transitions.data[state][alphabetDim] = lambdaTo;
        return ;
    }
        
    setLambdaClosure(lambdaTo,t,closure,checked);

    turnOn(closure,lambdaTo);
}

int
alreadySeen(int state, int originalDim, t_longInt l)
{
    t_longInt aux;
    
    if(state >= originalDim)
        return 0;
    
    reset(aux);
    turnOn(aux,state);
    longIntAnd(aux,l);
            
    return !isZero(aux);
}


int 
isFinalStInd(t_table *t, int state)
{
    int found, i;
    t_longInt word;
    
    longIntCpy(word, t->states.vec[state]);
    
    found = 0; // Needed in case vector is empty
    for (i = 0; i < t->finalStates.dim; i++)
        if (found = (longIntCmp(t->finalStates.vec[i], word)))
            break;
    
    return found;
}


